package _18_剑指OfferII;

import java.util.LinkedList;

public class _105_剑指OfferII岛屿的最大面积 {

    public static void main(String[] args) {

        _105_剑指OfferII岛屿的最大面积 v = new _105_剑指OfferII岛屿的最大面积();

        int[][] ins = {
                {1, 1, 0, 0, 0},
                {1, 1, 0, 0, 0},
                {0, 0, 0, 1, 1},
                {0, 0, 0, 1, 1},
        };

        System.out.println(v.maxAreaOfIsland(ins));

    }

    public int maxAreaOfIsland(int[][] grid) {
        int[][] m = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

        // 广度优先搜索
        int ans = 0;
        int row = grid.length;
        int col = grid[0].length;
        boolean[][] visited = new boolean[row][col];
        LinkedList<int[]> queue = new LinkedList<>();
        for (int i = 0; i < row; ++i) {
            for (int j = 0; j < col; ++j) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    int total = 1;
                    visited[i][j] = true;
                    queue.offer(new int[]{i, j});
                    while (!queue.isEmpty()) {
                        int[] poll = queue.poll();
                        for (int[] ints : m) {
                            int r = poll[0] + ints[0];
                            int c = poll[1] + ints[1];
                            if (r >= 0 && r < row && c >= 0 && c < col && grid[r][c] == 1 && !visited[r][c]) {
                                total++;
                                // 广度优先搜索，设置访问元素必须在添加元素这里，不能写在出元素外卖
                                visited[r][c] = true;
                                queue.offer(new int[]{r, c});
                            }
                        }
                    }
                    ans = Math.max(ans, total);
                }
            }
        }
        return ans;
    }

}
